package com.dataStructure;

import java.util.Arrays;

public class SortTest {

    /**
     * 选择排序
     *
     * @param arr
     * @return
     */
    public int[] choiceSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int temp;
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        return arr;
    }

    /**
     * 插入排序
     * @param arr
     * @return
     */
    public int[] insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                for (int j = i - 1; j >= 0; j--) {
                    int temp;
                    if (arr[i] > arr[j]) {
                        temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                        break;
                    }
                }
            }
        }

        return arr;
    }

    /**
     * 冒泡排序
     *
     * @param arr
     * @return
     */
    public int[] bubbleSort(int[] arr) {
//        for (int j = 0; j < arr.length-1; j ++) {
//            for (int i = j+1; i < arr.length; i++) {
//                if (arr[i] < arr[j]) {
//                    int temp = arr[j];
//                    arr[j] = arr[i];
//                    arr[i] = temp;
//                }
//            }
//        }
        int j = arr.length -1;
        while (j > 0) {
            for (int i = 0; i < j; i ++) {
                if (arr[i] > arr[i+1]) {
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1]=temp;
                }
            }
            j--;
        }

        return arr;
    }

    public int partition(int[] array, int first, int end) {
        int i = first;
        int j = end;
        while (i < j) {
            while (i<j && array[i] < array[j]) {
                j--;
            }
            if (i<j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
            }
            while (i<j&& array[i] < array[j]) {
                i++;
            }

            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] =temp;
                j--;
            }
        }
        return j;
    }

    public int[] quickSort(int[] arr, int first, int end) {
        if (first < end) {
            int pivot = partition(arr, first, end);
            quickSort(arr, first, pivot -1);
            quickSort(arr, pivot+1, end);
        }
        return arr;
    }


    public static void main(String[] args) {
        int[] arr = new int[7];

        arr[0] = 38;
        arr[1] = 65;
        arr[2] = 97;
        arr[3] = 76;
        arr[4] = 13;
        arr[5] = 27;
        arr[6] = 49;

        SortTest sortTest = new SortTest();

        System.out.println("选择排序");
        int[] result = sortTest.choiceSort(arr);

        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

        System.out.println();
        System.out.println("插入排序");
        result = sortTest.insertSort(arr);

        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

        System.out.println();
        System.out.println("冒泡排序");
        result = sortTest.bubbleSort(arr);

        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

        System.out.println();
        System.out.println("归并排序");
        Arrays.sort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

        System.out.println();
        System.out.println("归并排序");
        Arrays.parallelSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

        System.out.println();
        System.out.println("快速排序");
        result = sortTest.quickSort(arr, 0, arr.length -1);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+"\t");
        }

    }
}
